package lc.q1351_1400;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
 *
 * 你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。
 *
 * 请你返回你可以参加的 最大 会议数目。
 */
public class Q1351 {
    public int maxEvents(int[][] events) {
        int n = events.length;
        int maxDay = 0;
        for (int[] event : events) {
            maxDay = Math.max(maxDay, event[1]);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));
        int ans = 0;
        for (int i = 0, j = 0; i <= maxDay; i++) {
            // i是天数。循环查找会议安排，如果有会议早于今天的，当做候选，重新开始时无需reset，因为已经排序过
            while (j < n && events[j][0] <= i) {
                pq.offer(events[j][1]);
                j++;
            }
            // 如果候选小于当前的天数，则弹出
            while (!pq.isEmpty() && pq.peek() < i) {
                pq.poll();
            }
            // 此时，如果存在候选，那则可以放进去，并且弹出（选了这个活动作为会议安排）
            if (!pq.isEmpty()) {
                pq.poll();
                ans++;
            }
        }
        return ans;
    }
}
